

\subsection{Introducci'on}
Se instalan $n$ rociadores en una cancha de futbol de c'esped natural de $l$ metros de largo y $w$ metros de ancho. Cada rociador esta
instalado en la l'inea horizontal del centro de la cancha. Para cada uno de los rociadores se nos dice su posici'on como la distancia desde el extremo izquierdo de la l'inea central
y su radio de operaci'on. Se pide calcular el n'umero m'inimo de rociadores que se deben encender
para que la cancha de f'utbol sea regada completamente. Adicionalmente la complejidad temporal de la soluci'on debe ser estrictamente menor
a $O(n^{2})$
\begin{figure}[!h]
\centering
\includegraphics[scale=0.50]{secciones/graficos/ej2_cancha}
\caption{Planteo del problema}
\end{figure}

\subsection{Soluci'on}

Para encontrar el conjunto de c'irculos que cubren la cancha podemos ignorar la parte inferior de la misma ya que es sim'etrica a la superior
y adem'as proponemos una transformaci'on de c'irculos (el alcance real del rociador) a un subintervalo de la l'inea horizontal del centro
de la cancha. Este subintervalo representa la zona de la cancha que ese rociador puede alcanzar con seguridad cuando se lo combina con
otros. 

\begin{figure}[h!]
\centering
\includegraphics[scale=0.50]{secciones/graficos/ej2_trans}

	\caption{Intervalo que cubre un rociador}
\label{fig:ej2_trans}
\end{figure}

Como se ve en la figura \ref{fig:ej2_trans} las partes oscuras quedan sin cubrir por lo tanto la uni'on de ambos rociadores no siempre garantiza cubrir
toda su extensi'on. El subintervalo que si cubre la calculamos imaginando el centro de coordenadas en el comienzo de la l'inea horizontal del
centro de la cancha e intersecando $f(x)=\frac{w}{2}$ (es el l'imite superior de la cancha que como es de $w$ de ancho y  por el centro de
coordenadas que definimos, su posici'on es $\frac{w}{2}$) con la circunferencia delineada por el rociador la cual si su centro es $p$
(respecto a nuestro origen de coordenadas) y su radio es $r$ esta dada por $y^{2}+(x-p)^{2}=r^{2}$.

\begin{figure}[!h]
	\centering
\label{fig:ej2_int}
	\caption{Transformaci'on de c'irculos a intervalos}
\includegraphics[scale=0.85]{secciones/graficos/ej2_int}
\end{figure}

Luego podemos despejar $x$ haciendo reemplazasos y resolviendo:
\begin{eqnarray*}
(x-p)^{2}+(\frac{w}{2})^{2} & = & r^{2}\\
x^{2}-2px+(p^{2}+\frac{w{}^{2}}{4}-r^{2}) & = & 0\\
x & = & \frac{2p\pm\sqrt{4p^{2}-4p^{2}-w^{2}+4r^{2}}}{2}\\
x & = & p\pm\sqrt{r^{2}-\frac{w^{2}}{4}}\end{eqnarray*}


As'i, el intervalo ser'ia $(p-\sqrt{r^{2}-\frac{w^{2}}{4}},p+\sqrt{r^{2}-\frac{w^{2}}{4}})$.
Para cada c'irculo se calcula su intervalo asociado lo cual nos da una lista de intervalos que representan el area cubierta por un rociador, llamemoslo $S$.

Para encontrar el subconjunto de S tal que cubra $(0,l)$ usamos un algoritmo goloso el cual toma el primer intervalo tal que comience
a lo sumo en el 'ultimo punto ya cubierto y cubra la mayor cantidad de espacio todav'ia no cubierto.\\
\noindent

\bigskip

\noindent
\textbf{funci'on} buscarConjuntoMinimo($S$: array intervalos, $w$: entero)\\
$cubierto$= 0\\
$j$= 0\\
$cantidad$= 0\\
\n{\small1}mientras $j<|S|$ y $cubierto<w$\\
\n{\small2} \t buscar $j < i < |S|$ tal que $comienzo(S[i]) \leq cubierto$\\
%\n{\small2}\g buscar $I\subseteq S$ tal que $\forall i\in I,\, comienzo(i)\leq cubierto$ y $fin(i)>cubierto$
\t\t si hay mas de un $i$ posible \\
\n{\small3}\t\t\t tomar $i$ con $fin(i)$ m'as grande\\
\t\t si no existe $i$\\
\t\t\t  no hay soluci'on.\\
\t\t  $cubierto$ = $fin(S[i])$\\
\t\t $cantidad$ = $cantidad$ + 1\\
\t\t $j$ = $i$\\
fin mientras\\
devolver $cantidad$\\

\bigskip

Esto se puede hacer en \O{(n)} donde $n$ es la cantidad de intervalos en S si este est'a ordenado por la primera coordenada ya que el ciclo del paso 1 se ejecuta como m'aximo $n$ veces.
Si S esta ordenado los pasos 2 y 3 consisten en recorrer de menor a mayor S hasta que deje de valer que sea menor a $cubierto$, guardando en el camino el m'aximo punto cubierto para
actualizarlo. As'i los elementos de S se recorren 1 sola vez. Dado que ordenarlos tiene complejidad \O{(n log(n))} garantizado por la STL, ejecutar esta funci'on tiene complejidad 
\O{(n log(n) + n)} = \O{(n log(n))}.\\

La funci'on $buscarConjuntoMinimo$  encuentra el subconjunto de intervalos de tama~no m'inimo, la demostraci'on supone que $S_{opt} \subseteq  S$ cubre $(0,w)$
y $m=|S_{opt}| \leq |S\prime|$ $\forall   S\prime \subseteq S$ que cubren $(0,w)$. Sea $S_G$ el subconjunto que encuentra $buscarConjuntoMinimo$ usando el algoritmo goloso, suponemos
que $S_G$ no es el 'optimo. Tambi'en suponemos que $S_{opt}$ y $S_G$ est'an ordenados de menor a mayor seg'un la primera coordenada ($S_G$ lo esta por el m'etodo utilizado).
Si $S_{opt}$ es diferente a $S_G$ decimos que son iguales hasta que difieren en el elemento $j < m$, es decir ${S_{opt}}_j = (a_j, b_j) \neq {S_G}_j = (a\prime_j,b\prime_j) $.
Sabemos que $b\prime_j > b_j$ porque el algoritmo elige el candidato que cubre mas (ver figura \ref{fig:ej2_demo})

\begin{figure}[!h]
	\centering
\label{fig:ej2_demo}
	\caption{Demostraci'on, representaci'on gr'afica}
\includegraphics{secciones/graficos/ej2_demo}
\end{figure}

Si se diera el caso tal que $b\prime_j>b_j+1$ entonces en $S_{opt}$ puedo reemplazar ${S_{opt}}_j$ y ${S_{opt}}_{j+1}$ con ${S_G}_j$ logrando un subconjunto mas peque~no que el 'optimo, lo cual
es absurdo. De otra forma, si bien los intervalos son diferentes abarcan efectivamente el mismo espacio y se busca el pr'oximo 'indice donde difieran y se realiza el mismo an'alisis. Si
ning'un 'indice diferente se puede reemplazar entonces $|S_G|$=$|S_{opt}|$ y por ende el goloso encuenta un subconjunto que cubre lo mismo que el 'optimo con la misma cantidad de 
elementos, haci'endolo tambi'en 'optimo.


\subsection{Casos de test}
\begin{enumerate}
\item Casos donde se cubre a lo largo pero no toda la cancha. 
\begin{figure}[!h]
	\centering
\label{fig:ej2_caso1}
	\caption{Caso de test, no se cubre toda la cancha pero si el largo}
\includegraphics[scale=0.5]{secciones/graficos/ej2_trans}
\end{figure}
La figura \ref{fig:ej2_caso1} es un ejemplo de esta clase de casos, las partes grises no se cubren por los rociadores, el algoritmo
deber'ia decir que no existe soluci'on.


   \begin{tabular}{|p{5cm}|p{5cm}|}
      \hline
      Entrada & Salida \\
      \hline      
      2 10 6 & -1\\
      3 4 & \\
      7 4 &  \\
      \hline
      3 10 8 &  3\\ 
      5 6 & \\
      0 6& \\
      10 6& \\
      \hline
	\end{tabular}

\item Casos con el prop'osito de chequear la entrada tanto de ancho, altura, como n'umero de rociadores.
En los siguientes ejemplos se ingresa $l=0$ y $w=0$, o en su defecto s'olo uno de los par'ametros, 
\emph{l} o \emph{w}, igual a cero.\\

 	\begin{tabular}{|p{5cm}|p{5cm}|}
      \hline
      Entrada & Salida \\
      \hline      
      1 0 0 & 0 \\
      0 0 & \\
      \hline
      0 0 0 & 0 \\
      \hline
      2 10 0 & -1 \\ 
      4 1& \\
      8 1& \\
      \hline
      1 0 10 & 0 \\
      0 1 &\\
      \hline
    \end{tabular}

\item Este caso verifica que se tome la mejor desici'on cuando se ponen
dos rociadores en la misma posici'on.\\

	\begin{tabular}{|p{5cm}|p{5cm}|}
      \hline
      Entrada & Salida \\
      \hline      
      2 5 5 & 1 \\
      2 5 & \\
      2 20 &\\
      \hline
     \end{tabular}
    
\item Casos donde los rociadores, m'as cercanos a los bordes de la cancha, no llegan a cubrirlos.\\

    \begin{tabular}{|p{5cm}|p{5cm}|}
      \hline
      Entrada & Salida \\
      \hline
      2 5 0 & -1\\
      3 2 & \\
      5 4 & \\
      \hline
      2 5 0 & -1\\ 
      1 3 & \\
      3 1 & \\
      \hline
     \end{tabular}
\end{enumerate}

\newpage
